package leecode

import "sort"

func pondSizes(land [][]int) []int {
	var dfs func(land [][]int, row, column int) int
	dfs = func(land [][]int, row, column int) int {
		//判断是否超出边界
		if !isAreaM1619(land, row, column) {
			return 0
		}
		if land[row][column] != 0 {
			//遇见不是水域的区域则停止
			return 0
		}
		//上 , 下 , 左 , 右 , 上左 , 上右 , 下左 , 下右
		//遍历过的水域值标记为-1
		land[row][column] = -1
		//上
		return dfs(land, row, column-1) +
			//下
			dfs(land, row, column+1) +
			//左
			dfs(land, row-1, column) +
			//右
			dfs(land, row+1, column) +
			//上左
			dfs(land, row-1, column-1) +
			//上右
			dfs(land, row-1, column+1) +
			//下左
			dfs(land, row+1, column-1) +
			//下右
			dfs(land, row+1, column+1) + 1
	}
	var result []int
	for i := 0; i < len(land); i++ {
		for j := 0; j < len(land[i]); j++ {
			if land[i][j] == 0 {
				result = append(result, dfs(land, i, j))
			}
		}
	}
	sort.Ints(result)
	return result
}

// 判断是否超出边界范围
func isAreaM1619(land [][]int, row, column int) bool {
	return 0 <= row && row < len(land) && 0 <= column && column < len(land[0])
}
